#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=336 lang=cpp
 *
 * [336] 回文对
 */

// @lc code=start
class Solution {
public:


    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res; unordered_map<string, int> reverseDict;
        for (int i = 0; i < words.size(); i++) {
            string x = words[i];
            reverse(x.begin(), x.end());
            reverseDict[x] = i;
        }

        for (int i = 0; i < words.size(); i++) {
            int m = words[i].size();
            // xxxxasdasdsads
            // m - 1 - (i + 1) + 1
            for (int j = 0; j <= m; j++) {
                if (isPadrome(words[i], 0, j)) {
                    string x = words[i].substr(j + 1, m - j - 1);
                    if (reverseDict.count(x) && reverseDict[x] != i) res.push_back({reverseDict[x], i});
                }

            // aasdasdasdxxxxx
                if (isPadrome(words[i], j, m - 1)) {
                    string x = words[i].substr(0, j);
                    if (reverseDict.count(x)  && reverseDict[x] != i) res.push_back({i, reverseDict[x]});
                }
            }
        }
        return res;
    }

    bool isPadrome(const string & s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) return false;
            i++; j--;
        }
        return true;

    }
};
// @lc code=end

